package com.yww.leetcode.binarysearchtree;

import com.yww.leetcode.common.TreeNode;

/**
 * @author yww
 * @description 235. 二叉搜索树的最近公共祖先
 * @since 2024/2/17 16:29
 */
public class LowestCommonAncestor235 {
    // 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    // 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
    // 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大
    // （一个节点也可以是它自己的祖先）。”

    /**
     * 要点：若 p，q 在 ancestor 的两侧，则 ancestor 就是它们的最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while ((ancestor.val > p.val && ancestor.val > q.val) ||
                (ancestor.val < p.val && ancestor.val < q.val)) { // 在同一侧
            if (ancestor.val > p.val) {
                ancestor = ancestor.left;
            } else {
                ancestor = ancestor.right;
            }
        }
        return ancestor;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;

        return ancestor;
    }
}
